import sys
from collections import deque


def read_map(file_path):
    try:
        with open(file_path, 'r') as file:
            map_data = []
            for line in file:
                row = list(map(int, line.strip().split()))
                map_data.append(row)
        return map_data
    except FileNotFoundError:
        print(f"Error: Map file '{file_path}' not found.")
        sys.exit(1)
    except Exception as e:
        print(f"Error reading map file: {e}")
        sys.exit(1)


def is_valid_position(map_data, x, y):
    rows = len(map_data)
    cols = len(map_data[0]) if rows > 0 else 0
    return 0 <= x < rows and 0 <= y < cols and map_data[x][y] == 0


def bfs(map_data, start_x, start_y, goal_x, goal_y):
    # 检查起点和终点是否有效
    if not is_valid_position(map_data, start_x, start_y):
        print(f"I can't start at the position ({start_x},{start_y}).")
        return None

    if not is_valid_position(map_data, goal_x, goal_y):
        print(f"I can't go to the position ({goal_x},{goal_y}).")
        return None

    # 定义移动方向：上、右、下、左
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    # 初始化队列和访问矩阵
    queue = deque([(start_x, start_y)])
    visited = [[False for _ in range(len(map_data[0]))] for _ in range(len(map_data))]
    visited[start_x][start_y] = True

    parent = {}

    while queue:
        x, y = queue.popleft()

        if x == goal_x and y == goal_y:
            path = []
            while (x, y) != (start_x, start_y):
                path.append((x, y))
                x, y = parent[(x, y)]
            path.append((start_x, start_y))
            path.reverse()
            return path

        # 尝试四个方向
        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            if is_valid_position(map_data, nx, ny) and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx, ny))
                parent[(nx, ny)] = (x, y)

    # 如果没有找到路径
    print(f"I can't go to the position ({goal_x},{goal_y}).")
    return None


def print_map(map_data, path=None):

    for i in range(len(map_data)):
        for j in range(len(map_data[0])):
            if path and (i, j) in path:
                print('*', end=' ')
            else:
                print(map_data[i][j], end=' ')
        print()


def main():
    # 检查命令行参数
    if len(sys.argv) != 6:
        print("Usage: python bfs_maze.py <map_file_path> <start_x> <start_y> <goal_x> <goal_y>")
        sys.exit(1)

    # 解析命令行参数
    map_file = sys.argv[1]
    try:
        start_x = int(sys.argv[2])
        start_y = int(sys.argv[3])
        goal_x = int(sys.argv[4])
        goal_y = int(sys.argv[5])
    except ValueError:
        print("Error: Coordinates must be integers.")
        sys.exit(1)

    # 读取地图
    map_data = read_map(map_file)

    # 寻找路径
    path = bfs(map_data, start_x, start_y, goal_x, goal_y)

    # 打印结果
    if path:
        print_map(map_data, path)
    else:
        print_map(map_data)


if __name__ == "__main__":
    main()